package B刷题.链表;

/**
 * @author wei.zhao
 * @description: 剑指 Offer 35.复杂链表的复制
 * @date 2022年11月08日 14:55
 */
public class Code01_CopyRandomList {

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 将每个节点的next指向克隆的节点，克隆节点的next指向下一个节点
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            Node copyNode = new Node(cur.val);
            cur.next = copyNode;
            copyNode.next = next;
            cur = next;
        }
        // 为克隆节点random赋值
        cur = head;
        while (cur != null) {
            Node cloneNext = cur.next;
            cloneNext.random = cur.random == null ? null : cur.random.next;
            cur = cloneNext.next;
        }
        // 将链表拆分成两个
        Node result = head.next;
        cur = head;
        while (cur != null) {
            Node cloneNext = cur.next;
            Node realNext = cloneNext.next;
            Node cloneNextNext = realNext == null ? null : realNext.next;
            cur.next =realNext;
            cloneNext.next=cloneNextNext;
            cur=realNext;
        }
        return result;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
